package com.c2b.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/">二叉树的最近公共祖先</a>
 * <p>
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * <a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin">百度百科中最近公共祖先的定义</a>为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * </p>
 * <pre>
 * 示例 1：
 *      输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 *               3
 *             /   \
 *           5      1
 *          / \    / \
 *         6   2  0   8
 *            / |
 *           7  4
 *
 *      输出：3
 *      解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 *
 * 示例 2：
 *      输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 *               3
 *             /   \
 *           5      1
 *          / \    / \
 *         6   2  0   8
 *            / |
 *           7  4
 *
 *      输出：5
 *      解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 * 示例 3：
 *      输入：root = [1,2], p = 1, q = 2
 *                  1
 *                 /
 *                2
 *
 *      输出：1
 *
 * </pre>
 * <b>提示：</b>
 * <li>树中节点数目在范围 [2,10^5] 内。</li>
 * <li>-10^9 <= Node.val <= 10^9。</li>
 * <li>所有 Node.val 互不相同 。</li>
 * <li>p != q</li>
 * <li>p 和 q 均存在于给定的二叉树中。</li>
 *
 * @author c2b
 * @since 2023/4/21 14:28
 */
public class Hot236LowestCommonAncestor_M {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 用map保存整棵树上节点的父节点
        Map<Integer, TreeNode> parentNodeMap = new HashMap<>();
        buildParentNodeMap(root, null, parentNodeMap);
        final List<Integer> pPath = new ArrayList<>();
        while (p != null) {
            pPath.add(p.val);
            p = parentNodeMap.get(p.val);
        }
        while (q != null) {
            if (pPath.contains(q.val)) {
                return q;
            }
            q = parentNodeMap.get(q.val);
        }
        return null;
    }

    private void buildParentNodeMap(final TreeNode currentNode, final TreeNode parentNode, final Map<Integer, TreeNode> map) {
        if (currentNode != null) {
            map.put(currentNode.val, parentNode);
            buildParentNodeMap(currentNode.left, currentNode, map);
            buildParentNodeMap(currentNode.right, currentNode, map);
        }
    }
}
